`
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
`

/**
 * // Definition for a _Node.
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function (root) {
  if (root === null) return null

  // 用于存储上一个遍历的结点
  let lastNode = null

  const q = [root]

  while (q.length) {
    const sz = q.length
    for (let i = 0; i < sz; i++) {
      const cur = q.shift()
      if (cur.left) q.push(cur.left)
      if (cur.right) q.push(cur.right)
      // 如果有上一个结点，让上一个结点的 next 指向当前结点
      if (lastNode) lastNode.next = cur
      lastNode = cur
    }
    // 一层遍历完后，重置 lastNode
    lastNode = null
  }

  return root
};